/**
 * 单端队列
 *
 * 队列形状
 *         头部                                            尾部
 *  value:  1 <-------- 2 <-------- 3 <-------- 4 <-------- 5
 *  key:    0           1           2           3           4
 *  lowestCount 指向头部第一个元素的索引（key值）,也就是这里1的key值=0
 */
class Queue {
  constructor() {
    this.count = 0
    // 指向头部的索引，队列中头部的第一个元素
    this.lowestCount = 0
    this.items = {}
  }

  /**
   * 向尾部添加一个或多个新的项
   * @param element
   */
  enqueue(element) {
    this.items[this.count] = element
    this.count++
  }

  /**
   * 从队列头部移除元素，先进先出原则
   * @returns {undefined|*}
   */
  dequeue() {
    if (this.isEmpty()) {
      return undefined
    }

    const result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return result
  }

  /**
   * 查看队列头元素
   * @returns {undefined|*}
   */
  peek() {
    if (this.isEmpty()) {
      return undefined
    }

    return this.items[this.lowestCount]
  }

  isEmpty() {
    return this.count - this.lowestCount === 0
  }

  size() {
    return this.count - this.lowestCount
  }

  clear() {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  toString() {
    if (this.isEmpty()) {
      return ''
    }
    let objString = `${this.items[this.lowestCount]}`
    for (let i = this.lowestCount; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`
    }
    return objString
  }
}

/**
 * 双端队列
 */
class Deque extends Queue {
  constructor() {
    super()
  }

  /**
   * 在前端添加新元素
   * @param element
   */
  addFront(element) {
    if (this.isEmpty()) {
      this.enqueue(element)
    } else if (this.lowestCount > 0) {
      this.lowestCount--
      this.items[this.lowestCount] = element
    } else {
      // 所有元素往后退一格
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1]
      }
      // 队列长度加1
      this.count++
      // lowestCount 指向第一个，感觉这句话没必要写
      this.lowestCount = 0
      // 头部加入第一个元素
      this.items[0] = element
    }
  }

  /**
   * 移除尾部最后一个元素
   */
  removeBack() {
    if (this.isEmpty()) {
      return undefined
    }

    const result = this.items[this.count - 1]
    delete this.items[this.count - 1]
    this.count--
    return result
  }

  /**
   * 返回尾部最后一个元素
   */
  peekBack() {
    if (this.isEmpty()) {
      return undefined
    }

    return this.items[this.count - 1]
  }
}

module.exports = {
  Queue,
  Deque
}
